package com.wangzemin.leetcode.num86;


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode leftHead = new ListNode();
        ListNode rightHead = new ListNode();
        ListNode curLeft = leftHead;
        ListNode curRight = rightHead;

        while (head!=null){
            ListNode curVal = head;
            head = head.next;
            curVal.next = null;
            if (curVal.val<x){
                curLeft.next = curVal;
                curLeft = curLeft.next;
            }else {
                curRight.next = curVal;
                curRight = curRight.next;
            }

        }
        curLeft.next = rightHead.next;
        return leftHead.next;
    }
}